/*
 * BinTree.cpp
 *
 *  Created on: 2014年6月10日
 *      Author: rock
 */

#include "BinTree.h"
#include "common.h"
#include "Queue.h"
#include "Stack.h"

using namespace std;

TreeNode * BuildBinaryTree(TreeNode* root, int level)
{
	if(level-- <= 0)
		return NULL;

	if(root == NULL)
		root = new TreeNode(generateRandom());

	cout << root->data << "  ";

	TreeNode * left = NULL;
	TreeNode * right = NULL;

#if 1
	if(root->data > 850)
	{
		left = BuildBinaryTree(NULL, level);
	}
	else if(root->data < 150)
	{
		right =  BuildBinaryTree(NULL, level);
	}
	else
	{
		left = BuildBinaryTree(NULL, level);
		right = BuildBinaryTree(NULL, level);
	}
#else
	left = BuildBinaryTree(NULL, level);
	right = BuildBinaryTree(NULL, level);
#endif

	root->leftchild = left;
	root->rightchild = right;

	return root;
}

int CalcTreeDepth(TreeNode* root )
{
	if(root == NULL)
		return 0;
	
	int leftDepth = CalcTreeDepth(root -> leftchild);
	int rightDepth = CalcTreeDepth(root -> rightchild);

	return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

//前序遍历
void PreOrderTree(TreeNode * root)
{
	if(root == NULL)
	{
		return;
	}

	cout << root->data << "  ";
	PreOrderTree(root->leftchild);
	PreOrderTree(root->rightchild);

}

//中序遍历
void MidOrderTree(TreeNode * root)
{
	if(root == NULL)
	{
		return;
	}

	MidOrderTree(root->leftchild);
	cout << root->data << "  ";
	MidOrderTree(root->rightchild);
}

//后序遍历
void PostOrderTree(TreeNode * root)
{
	if(root == NULL)
	{
		return;
	}

	PostOrderTree(root->leftchild);
	PostOrderTree(root->rightchild);
	cout << root->data << "  ";
}

void PreOrderTreeIterater(TreeNode * root)
{
	//提前退出
	if(root == NULL)
		return;

	TreeNode * node = root;

	Stack<TreeNode*> * myStack = new Stack<TreeNode*>();

	while(node || !myStack->isEmpty())
	{
		while(node)
		{
			cout << node->data << "  ";
			myStack->push(node);
			node = node->leftchild;
		}
		
		if(!myStack->isEmpty())
		{
			node =  myStack->pop();
			node = node->rightchild;
		}

	}

	delete myStack;
}

void MidOrderTreeIterater(TreeNode * root)
{
	//提前退出
	if(root == NULL)
		return;

	TreeNode * node = root;

	Stack<TreeNode*> * myStack = new Stack<TreeNode*>();

	while(node || !myStack->isEmpty())
	{
		while(node)
		{
			myStack->push(node);
			node = node->leftchild;
		}
		
		if(!myStack->isEmpty())
		{
			node = myStack->pop();
			cout << node->data << "  ";
			node = node->rightchild;
		}
	}

	delete myStack;
}
/**
 * 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
 * 如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，
 * 则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，
 * 左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
 */


void PostOrderTreeIterater(TreeNode * root)
{
	//提前退出
	if(root == NULL)
		return;

	Stack<TreeNode*> * myStack = new Stack<TreeNode*>();

	TreeNode * cur;                      //当前结点 
	TreeNode * pre = NULL;                 //前一次访问的结点 
	myStack->push(root);

	while(!myStack->isEmpty())
	{
		//Get the Top element.
		cur = myStack->pop();
		myStack->push(cur);

		if( ( ( cur->leftchild == NULL ) && ( cur->rightchild == NULL) )
		  || (    pre != NULL 
			  && (pre == cur->leftchild/*没有右结点*/ || pre == cur->rightchild)
			 )          
		  )
		{
			cout << cur->data << "  ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
			myStack->pop();
			pre = cur; 
		}
		else
		{
			if(cur->rightchild != NULL)
				myStack->push(cur->rightchild);
			if(cur->leftchild != NULL)    
				myStack->push(cur->leftchild);
		}

	}

	delete myStack;
}

void LevelOrderTree(TreeNode *root)
{
	if(root == NULL)
	{
		return;
	}

	Queue<TreeNode*> NodeQueue;

	NodeQueue.add(root);

	while(1)
	{
		TreeNode * curNode = NodeQueue.remove();
		if(curNode)
		{
			cout<< curNode->data << "  " ;
			if(curNode->leftchild)
				NodeQueue.add(curNode->leftchild);

			if(curNode->rightchild)
				NodeQueue.add(curNode->rightchild);

		}
		else
			break;
	}
}
